package mine.code.day.year2021.month09;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 * <p>
 * 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * 输出："apple"
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "abpcplea", dictionary = ["a","b","c"]
 * 输出："a"
 *
 * @author caijinnan
 */
public class Day14_通过删除字母匹配到字典里最长单词 {


    @Test
    public void run() {
        String s = "abpcplea";
        String[] dict = {"ale", "apple", "monkey", "plea"};
        System.out.println(findLongestWord(s, Arrays.asList(dict)));

    }


    public String findLongestWord(String s, List<String> dictionary) {
        String[] dictArr = dictionary.toArray(new String[0]);
        Arrays.sort(dictArr);
        String result = "";
        int maxLength = 0;
        for (String dict : dictArr) {
            char[] dictChars = dict.toCharArray();
            char[] sChars = s.toCharArray();
            int i = 0, j = 0;
            while (i < dictChars.length && j < sChars.length) {
                if (dictChars[i] == sChars[j]) {
                    ++i;
                }
                ++j;
            }
            if (i == dict.length() && i > maxLength) {
                result = dict;
                maxLength = i;
            }
        }
        return result;
    }
}
